import java.util.Deque;
import java.util.LinkedList;

public class offer052 {
    //展平二叉树
    Deque<TreeNode> deque = new LinkedList<>();
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummyhead = new TreeNode();
        TreeNode cur = dummyhead;
        inorder(root);
        while (!deque.isEmpty()) {
            TreeNode node = new TreeNode(deque.poll().val);
            cur.right = node;
            cur = cur.right;
        }
        return dummyhead.right;
    }

    private void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        deque.offer(root);
        inorder(root.right);
    }
}
